package com.sheng.leetcode.year2025.month08.day11;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author by ls
 * @date 2025/8/11
 * <p>
 * 2438. 二的幂数组中查询范围内的乘积<p>
 * <p>
 * 给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含 最少 数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。<p>
 * 同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, righti] ，其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。<p>
 * 请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10^9 + 7 取余 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 15, queries = [[0,1],[2,2],[0,3]]<p>
 * 输出：[2,4,64]<p>
 * 解释：<p>
 * 对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。<p>
 * 第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。<p>
 * 第 2 个查询的答案：powers[2] = 4 。<p>
 * 第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。<p>
 * 每个答案对 10^9 + 7 得到的结果都相同，所以返回 [2,4,64] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 2, queries = [[0,0]]<p>
 * 输出：[2]<p>
 * 解释：<p>
 * 对于 n = 2, powers = [2] 。<p>
 * 唯一一个查询的答案是 powers[0] = 2 。答案对 10^9 + 7 取余后结果相同，所以返回 [2] 。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 10^9<p>
 * 1 <= queries.length <= 10^5<p>
 * 0 <= starti <= endi < powers.length<p>
 */
public class LeetCode2438 {

    @Test
    public void test() {
//        int n = 15;
//        int[][] queries = {{0, 1}, {2, 2}, {0, 3}};
//        int n = 2;
//        int[][] queries = {{0, 0}};
        int n = 13;
        int[][] queries = {{1, 2}, {1, 1}};
        int[] answers = new Solution().productQueries(n, queries);
        for (int answer : answers) {
            System.out.println(answer);
        }
    }
}

class Solution {

    private static final int MOD = 1000000007;

    public int[] productQueries(int n, int[][] queries) {
        List<Integer> results = new ArrayList<>();

        int m = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                results.add(m);
            }
            n >>= 1;
            m *= 2;
        }
        // 1. 先对 List 进行排序（从小到大）
        Collections.sort(results);

        // 2. 将排序后的 List 转换成数组
        int[] powers = results.stream().mapToInt(Integer::intValue).toArray();

        int[] answers = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            long j = 1;
            for (int i1 = queries[i][0]; i1 <= queries[i][1]; i1++) {
                j = j * powers[i1] % MOD;
            }
            answers[i] = (int) j;
        }
        return answers;
    }
}
